// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-30 15:47
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

public class MaxConsecutiveAnswers {
    /**
     * 考试的最大困扰度
     */
    public int maxConsecutiveAnswersT(String answerKey, int k) {
        // 1 朴素解法 --> 分类讨论
        int TNums = getNums(answerKey, k, 'T');
        int FNums = getNums(answerKey, k, 'F');
        return Math.max(TNums, FNums);
    }

    /**
     * 使用滑动窗口确定答案的最大困扰度
     */
    private int getNums(String answerKey, int k, char c) {
        int n = answerKey.length();
        int l = 0, r = 0, res = 0;
        while (r < n) {
            /*
                 两种情况：char(r) == c || char(r) != c
                 一种情况比较好解决，另一种情况又可以分情况讨论
             */
            char cur = answerKey.charAt(r);
            int nums = r - l + 1;
            if (cur != c) {
                /*
                    窗口右边界值不等于预期值，分两种情况：
                        1 容错值存在
                        2 容错值不存在
                 */
                // 容错阈值为0，需要调整窗口左边界
                while (k <= 0) {
                    if (answerKey.charAt(l) != c) {
                        k++;
                    }
                    l++;
                    nums--;
                }
                k--;
            }
            res = Math.max(res, nums);
            r++;
        }
        return res;
    }

    /**
     * 滑动窗口解法
     */
    public int maxConsecutiveAnswers(String answerKey, int k) {
        /*
            窗口饱和阈值-> 窗口中每一个一个元素数量都超过容错阈值
            窗口饱和之后的操作->将窗口中其中一个元素的数量降到容错阈值之下
         */
        int TNum = 0, FNum = 0, L = 0, R = 0, n = answerKey.length(), res = 0;
        while (R < n) {
            if (answerKey.charAt(R) == 'T') {
                ++TNum;
            } else {
                ++FNum;
            }
            while (TNum > k && FNum > k) {
                // 窗口饱和
                if (answerKey.charAt(L++) == 'T') {
                    TNum--;
                } else {
                    FNum--;
                }
            }
            res = Math.max(res, R - L + 1);
            R++;
        }
        return res;
    }
}
